package tree;

import java.util.Scanner;
//ACM题,从头到尾要能够输出运行
//用户输入一串先序遍历的字符串,根据字符串生成一个的二叉树,再对二叉树进行中序遍历,并输出结果
//用户输入是abc##de#f##g###,#表示空格,空格字符代表空树
// (这里不确定用户到底输入的是#还是空格,因此可以做两手准备)
//另外,输出时要每个字符后面都有一个空格,每个结果占一行
public class Main {
    static class Node{
        public char val;
        Node left;
        Node right;
        public Node(char val){
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextLine()){
            String line = in.nextLine();
//            1.构建出二叉树
            Node root = build(line);
//            2.中序遍历打印二叉树的节点
            InOrder(root);
            System.out.println();
            //题目要求每次的结果都占一行,这个一定不能忘,写到主函数是最好的选择,因为InOrder还要不断递归
            index = 0;
        }
    }

    //这里的build是需要递归的,因此在方法内部创建index局部变量的话,这个变量的值会在递归过程中不断创出来新的
    //因此就把index创建为全局变量

    public static int index = 0;
    public static Node build(String s){
        char c = s.charAt(index);
        //做两手准备
        if(c == '#' || c == ' '){
            return null;
        }
        Node root = new Node(c);
        index++;
        root.left = build(s);
        index++;
        root.right = build(s);
        return root;
    }

    public static void InOrder(Node root){
        if(root == null){
            return;
        }
        InOrder(root.left);
        System.out.print(root.val + " ");
        InOrder(root.right);
    }
}
